The present invention relates to a vector quantizer and, more particularly, to a vector quantizer for low bit rate coding time-sequential signals such as speech signals and image signals.
Vector quantization is a typical method of quantizing time-series signals such as speech signals and image signals by dividing the input signal into a plurality of frames with a predetermined interval (or blocks with a predetermined area). The vector quantization is excellent in the quantization performance in the sense that this method can reduce the quantizing distortion with respect to the number of assigned bits. This method, however, requires great deals of computational effort and storage capacity for the retrieval of an optimum quantization output vector which best represents the quantization signal.
For example, in vector quantization with 0.5 bit per sample and 40 vector dimensions, the computational effort (i.e., number of AND/ORing times) and storage capacity for the retrieval are 40.times.20.sup.2 per vector. This means that where a speech signal of 8 Khz sampling is dealt with, the computational effort is a little higher than about 1660.times.10.sup.6 per second. This operational scale is impossible with a single chip of DSP (Digital Signal Processor).
In the case of possible application of a plurality of high bit rate DSPs in parallel, increases of the price, power consumption, installation area, etc. are inevitable, thus disabling the application of the method to portable terminals or the like.
Various methods for executing vector quantization with less computational scales have heretofore been investigated. A basic method for the computational scale reduction is "structuring", in which some restrictions are provided among codevectors constituting a vector quantizer.
A typical method of structuring is vector sum quantization, which is disclosed in Japanese Patent Laid-Open Heisei 2-502135. Among other typical methods of structuring is lattice vector quantization as shown in, for instance, J. H. Conway and N. J. A. Sloane, "First Quantizing and Decoding Algorithms for Lattice Quantizers and Codes", IEEE Trans. Inf. Theory, Vol. IT-28, pp. 227-232, 1982, and R. M. Gray Source Coding Theory, Ch. 5.5, Kluwer Academic Publishers, 1990.
These vector quantizers feature in generation of codevectors by arithmetic operations of predetermined base vectors with or without multiplification by an integer. Specifically, denoting M base vectors by{a.sub.i, i=1, . . . ,M}, a k-th codebook is given as: ##EQU1## where {u.sub.ki } is integers. In the vector sum quantization, the coefficient u.sub.ki take as values of "1" or "-1", and 2.sup.M vectors are generated.
In such a vector quantization, the computational effort can be greatly reduced by providing appropriate contrivances with respect to the character of the arithmetic operations and the retrieval sequence so long as the number M of the base vectors is considerably small compared to the number L of the vector dimensions. For example, the computational effort in the vector quantization is reduced by providing the following contrivance in the retrieval step.
Denoting an n-th frame input vector by x.sub.n, base vectors by {a.sub.i, i=1, . . . ,M}, the coefficient vector of a k-th codevector by {u.sub.ki, i=1, . . . ,M}, a k-th codebook is retrieved by using an evaluating function J.sub.k given as: ##EQU2## where t attached to ai indicates transposition.
It is assumed that u.sub.ki is "1" when an i-th bit is "0" for k expressed by the binary expression and "-1" when the i-th bit is "1" and that EQU u.sub.(k+1)i =-u.sub.ki and EQU u.sub.(k+1)j =u.sub.kj (j.noteq.i).
Then, J.sub.k and (k+1)-th evaluating function J.sub.k+1 are related as: ##EQU3##
By setting L as the vector dimension number, the computational effort (number of AND/ORing times) C.sub.vsum that is required for the retrieval in this case is: EQU C.sub.vsum =L+ML+(1/2)M(M+1)L+(2.sup.M-1 -1) +M(2.sup.M-1 -1) (4)
The AND/ORing times number C.sub.norm that is necessary for the usual vector quantizer is EQU C.sub.norm =L2.sup.M.
Thus, if EQU M&lt;&lt;L,
we have EQU C.sub.vsum &lt;&lt;C.sub.norm.
The above prior art quantizing systems such as the vector sum quantizing system and the lattice vector quantizing system, feature in that the computational effort for the codevector retrieval can be greatly reduced. In these vector quantizing systems, however, codevectors are generated by arithmetic operations of base vectors with or without multiplification by an integer. Therefore, the codevector generation is greatly restricted, and the quantizers are greatly inferior in performance to non-structured vector quantizers.
For example, it was reported that with respect to speech signals the vector sum quantization is inferior in performance by 2 dB or more at 8 kb/s to the non-structured vector quantization (LeBlanc, W. P and Mahmound, S. A., "Structured Codebook Design in CELP", Proc. International Mobile Satellite Conference, p. 667-672, 1991).